package chapter07;

import chapter02.MyUtil;

public class FlowShop {
    //批处理作业调度
    private int n;//作业数
    private int[][] m;//作业所需处理时间
    private int[] x;//当前作业调度
    private int f1;
    private int[] f2;
    private int f;
    public int bestf;
    public int[] bestx;
   public FlowShop(int[][] m){
       n=m.length-1;
       this.m=m;
       bestf=Integer.MAX_VALUE;
       x=new int[n+1];
       bestx=new int[n+1];
       f2=new int[n+1];
       for (int i = 1; i <= n; i++)
           x[i]=i;
       backtrack(1);


   }
   public void backtrack(int i){
       if (i>n){
           for (int j = 1; j <= n; j++)
               bestx[j]=x[j];

           bestf=f;
       }else {
           for (int j = i; j <=n; j++) {
               f1+=m[x[j]][1];
               f2[i]=((f2[i-1] > f1) ? f2[i-1] : f1)+m[x[j]][2];
               f+=f2[i];
               if(f<bestf){
                   MyUtil.swap(x,i,j);
                   backtrack(i+1);
                   MyUtil.swap(x,i,j);
               }
               f1-=m[x[j]][1];
               f-=f2[i];
           }
       }
   }

    public static void main(String[] args) {
       //int[][] m={{2,1},{3,1},{2,3}};
        int[][] m={{0,0,0},{0,2,1},{0,3,1},{0,2,3}};
//        int[][] m=new int[4][3];
//        m[1][1]=2;
//        m[2][1]=3;
//        m[3][1]=2;
//        m[1][2]=1;
//        m[2][2]=1;
//        m[3][2]=3;
        FlowShop flowShop = new FlowShop(m);
        System.out.println(flowShop.bestf);
        MyUtil.printA(flowShop.bestx,1);

    }


}
